package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1606 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
            TreeSet<Integer> availableIdSet = new TreeSet<>();
            PriorityQueue<int[]> busySet = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];// int[] 0 存id，1 存 完成时间
                }
            });

            for (int i = 0; i < k; i++) availableIdSet.add(i);
            int[] workCnt = new int[k];
            for (int i = 0; i < arrival.length; i++) {
                int start = arrival[i], end = load[i] + arrival[i];
                while (!busySet.isEmpty() && busySet.peek()[1] <= start) {
                    availableIdSet.add(busySet.poll()[0]);
                }

                if (availableIdSet.isEmpty()) continue;
                Integer matchServerId = availableIdSet.ceiling(i % k);
                if (null == matchServerId) matchServerId = availableIdSet.pollFirst();
                else availableIdSet.remove(matchServerId);

                workCnt[matchServerId]++;
                busySet.add(new int[]{matchServerId, end});
            }

            Map<Integer, List<Integer>> workMap = new TreeMap<>(Comparator.reverseOrder());
            for (int i = 0; i < k; i++) {
                if (!workMap.containsKey(workCnt[i])) workMap.put(workCnt[i], new ArrayList<>());
                workMap.get(workCnt[i]).add(i);
            }

            return workMap.values().iterator().next();
        }
    }

    public void run() {
        System.out.println(new Solution().busiestServers(3, InputUtil.toIntegerArray("[1,2,3,4,5]"), InputUtil.toIntegerArray("[5,2,3,3,3]")));
        System.out.println(new Solution().busiestServers(3, InputUtil.toIntegerArray("[1,2,3,4]"), InputUtil.toIntegerArray("[1,2,1,2]")));
        System.out.println(new Solution().busiestServers(3, InputUtil.toIntegerArray("[1,2,3]"), InputUtil.toIntegerArray("[10,12,11]")));
        System.out.println(new Solution().busiestServers(3, InputUtil.toIntegerArray("[1,2,3,4,8,9,10]"), InputUtil.toIntegerArray("[5,2,10,3,1,2,2]")));
        System.out.println(new Solution().busiestServers(1, InputUtil.toIntegerArray("[1]"), InputUtil.toIntegerArray("[1]")));
        System.out.println(new Solution().busiestServers(7, InputUtil.toIntegerArray("[1,3,4,5,6,11,12,13,15,19,20,21,23,25,31,32]"), InputUtil.toIntegerArray("[9,16,14,1,5,15,6,10,1,1,7,5,11,4,4,6]")));
    }

    public static void main(String[] args) throws Exception {
        LC1606 an = new LC1606();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
